823. 带因子的二叉树

Solution Tips

方案一: Dp

var numFactoredBinaryTrees = function(arr) {
    // 和之前的二叉树方案数类似
    // 但是这次只能保存有因数的节点
    // 每个元素作为根节点都是最基础的一种, 是否需要纳入 dp[i] 的考量呢?
    // 把该元素分解因数, 因数必须在 arr 内, 则满足条件可以作为一棵子树
    // 先进行排序, 保证每个因数只需要考虑前面出现过的元素
    arr.sort((a, b) => a - b);
    // 哈希表记录
    const map = {};
    for (let i = 0; i < arr.length; i++) {
        // 不重复
        map[arr[i]] = i;
    }

    // dp[i] 为以第 i 个元素为根节点, 满足题意的二叉树的个数, 最少有一个满足题意
    const dp = Array.from({ length: arr.length }, () => 1);

    for (let i = 0; i < arr.length; i++) {
        const root = arr[i];
        for (let j = 0; j < i; j++) {
            // 0 - i 满足分解因数的节点可以作为子节点
            // 存在性判断, 使用哈希表
            const factor = root / arr[j];
            if (map[factor] !== undefined) {
                // arr[j] 和 factor 构成 root 的两个子节点
                // 等于两个子节点的方案数相乘
                // dp[i] = arr[j] === factor ? (dp[arr[j]] * dp[factor]) + 1 : (dp[arr[j]] * dp[factor]) + 2
                // root 10, 5 2, 分别遍历, 所以要加上 dp[i]
                dp[i] = (dp[j] * dp[map[factor]]) + dp[i]
            }

            // 如果不存在, 好像没啥特别的
        }
    }

    // return dp sum
    return dp.reduce((acc, val) => acc + val, 0)  % (Math.pow(10, 9) + 7)
};

如果想要在 On 查询完 dp, 需要知道 root 所有的因数, 然后直接读取哈希表就可以了

823. 带因子的二叉树

Similar Question

Solution Tips

方案一: Dp